KMP

发表于 | 分类于

KMP 字符串匹配算法


“The Linux philosophy is “Laugh in the face of danger”.Oops.Wrong One. “Do it yourself”. Yes, that”s it.”
Linux的哲学就是“在危险面前放声大笑”，呵呵，不是这句，应该是“一切靠自己，自力更生”才对。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package Algorithm;

public class KMP {
    public static int kmp (String target, String pattern) {
        int i = 0, j = 0;
        int res = 0;
        int[] next = getNextArray2(pattern);
        while (i < pattern.length() && j < target.length()) {
            if (i == -1 || pattern.charAt(i) == target.charAt(j)) {
                i++;
                j++;
            } else {
                /** 回退
                 * ABCDABD
                 * 如最后一位没有匹配到，则需回退到下标2
                 */
                i = i - 1 > 0 ? next[i - 1] : -1;
            }
        }
        if (i == pattern.length())
            return j;
        else
            return -1;
    }

    /**
     * 计算出的数组A表示以这一位位阶为的最长前后缀
     * 而next数组则为数组A右移一位，第一个值赋为-1
     * 如ABCDABD
     * getNextArray计算出来：0 0 0 0 1 2 0
     * 真正的next：-1 0 0 0 0 1 2
     */
    public static int[] getNextArray (String pattern) {
        int[] next = new int[pattern.length()];
        next[0] = 0;
        for (int i = 1; i < pattern.length(); i++) {
            /**
             *    ABCABD
             *    判断D与C是否相等
             *    类似于动态规划
             */
            if (pattern.charAt(next[i - 1]) == pattern.charAt(i))
                next[i] = next[i - 1] + 1;
            else {
                /**
                 * 不相等，递归next
                 * ABABCABABD
                 * D不等于C,递归next[C的下标 - 1]
                 */
                int j = next[i - 1];
                while (j > 0) {
                    if (pattern.charAt(j) == pattern.charAt(i))
                        next[i] = j + 1;
                    else
                        j = next[j-1];
                }
                if (j == 0 && pattern.charAt(0) == pattern.charAt(i))
                    next[i] = 1;
                else
                    next[i] = 0;
            }
        }
        return next;
    }
    //直接求next数组
    public static int[] getNextArray2 (String pattern) {
        int[] next = new int[pattern.length()];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < pattern.length()-1) {
            if (j == -1 || pattern.charAt(j) == pattern.charAt(i)) {
                ++i;
                ++j;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

        public static void main (String[]args){
            KMP.kmp("BBC_ABCDAB_ABCDABCDABDE", "ABABBCABB");
        }
    }
Thanks!